/*
 * @Author: lei
 * @Description: 归并排序示例
 * @FilePath: /code/mergesort.cc
 */
#include <iostream>
#include <vector>
using namespace std;
// g++ -o mergesort mergesort.cc -std=c++11 -g
// [l,r]为待排序序列下标范围
void MergeSort(vector<int>& v, int l, int r) {
  if (l >= r) return;
  int mid = l + (r - l) / 2;
  MergeSort(v, l, mid);
  MergeSort(v, mid + 1, r);
  // tmp为临时存放中间结果的辅助数组
  vector<int> tmp(v.begin() + l, v.begin() + l + r + 1);
  //   vector<int> tmp(r - l + 1);
  //   for (int k = l; k <= r; k++) {
  //     tmp[k - l] = v[k];
  //   }
  int i = 0, j = mid - l + 1;  // i,j分别为两个归并序列的第一个元素的下标
  for (int k = l; k <= r; k++) {
    if (i == mid - l + 1)
      v[k] = tmp[j++];
    else if (j == r - l + 1 || tmp[i] <= tmp[j])
      v[k] = tmp[i++];
    else
      v[k] = tmp[j++];
  }
}

int main() {
  vector<int> v{1, 8, 3, 89, 0, -342, 90, -87, 987};
  for (auto& t : v) cout << t << " ";
  cout << endl;
  MergeSort(v, 0, v.size() - 1);
  for (auto& t : v) cout << t << " ";
  cout << endl;
  return 0;
}